package codingInterview.leetcode.editor.cn;

////////输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相
//同。
//// 
////////
//////// 
////////
//////// 参考以下这颗二叉搜索树： 
////////
//////// 5
//////// / \
//////// 2 6
//////// / \
//////// 1 3 
////////
//////// 示例 1： 
////////
//////// 输入: [1,6,3,2,5]
////////输出: false 
////////
//////// 示例 2： 
////////
//////// 输入: [1,3,2,6,5]
////////输出: true 
////////
//////// 
////////
//////// 提示： 
////////
//////// 
//////// 数组长度 <= 1000 
//////// 
//////// Related Topics 栈 树 二叉搜索树 递归 二叉树 单调栈 👍 452 👎 0
//////
////
//

//Java：剑指 Offer 33 - 二叉搜索树的后序遍历序列
public class ErChaSouSuoShuDeHouXuBianLiXuLieLcof{
    public static void main(String[] args) {
                Solution solution = new ErChaSouSuoShuDeHouXuBianLiXuLieLcof().new Solution();
        // TO TEST
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean verifyPostorder(int[] postorder) {
        if(postorder.length<2) return true;
        return verify(postorder,0, postorder.length-1);
    }

    private boolean verify(int[] postorder, int start, int end){
        if(start>=end) return true; //只有一个节点
        int root = postorder[end];
        int left=start;
        while (postorder[left]<root && left<end){
            left++;
        }
        int right=left;
        while (right<end){
            if(postorder[right]<root)
                return false;
            right++;
        }
        return verify(postorder,start,left-1) && verify(postorder,left,end-1);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
